#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/**
 * 有序数组  二分搜索法
 * [O(nlogn), O(1)]
 */
class Solution{
	public:
		vector<int> twoSum(vector<int>& numbers, int target){
			assert(numbers.size() >= 2);
			for(int i = 0;i < numbers.size() - 1; ++i){
				int j = binarySearch(numbers, i + 1, numbers.size()-1,target -numbers[i]);
				if(j != -1){
					int res[2] = {i + 1, j + 1};
					return vector<int>(res, res + 2);
				}
			}
			throw invalid_argument("the input has no solution");

		}
	private:
		int binarySearch(const vector<int> &nums, int l, int r, int target){
			assert(l >= 0 && l < nums.size());
			assert(r >= 0 && r < nums.size());
			while(l <= r){
				int mid = l + (r - l)/2;
				if(nums[mid] == target){
					return mid;
				}

				if(target > nums[mid]){
					l = mid + 1;
				}else{
					r = mid - 1;
				}
			}

			return -1;
		}
};
